package com.agile.leetcode.tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 两棵树重复是指它们具有相同的结构以及相同的结点值。
 *
 * 示例 1：
 *
 *         1
 *        / \
 *       2   3
 *      /   / \
 *     4   2   4
 *        /
 *       4
 *
 * 下面是两个重复的子树：
 *
 *       2
 *      /
 *     4
 *
 * 和
 *
 *     4
 *
 * 因此，你需要以列表的形式返回上述重复子树的根结点。

 *
 */
public class RepeatTree {
   //数字相同
    Set<String> set=new HashSet<>();
    Set<String> set1=new HashSet<>();
    List<String> list=new ArrayList<>();
    public Set<String> preNode(Node node){
        if (node!=null){
            boolean add = set.add(node.getData());
            list.add(node.getData());
            if (!add&&node.getLeftNode()==null&&node.getRightNode()==null){
                set1.add(node.getData());
            }
            preNode(node.getLeftNode());
            preNode(node.getRightNode());
        }
        return set1;
    }
    public List<String> getList(){
        return list;
    }
    public Set<String> getSet(List<String> list){
        Set<String> set=new HashSet<>();
        int size = list.size();
        String str="";
        for (String s : list) {
            str+=s;
        }
        for (int i=0;i<size;i++){
            for (int j=i+1;j<size;j++){
                String substring = str.substring(j);
                StringBuffer stringBuffer=new StringBuffer();
                for (int m=i;m<=j;m++){
                    stringBuffer.append(list.get(m));
                }
                if (substring.contains(stringBuffer.toString())){
                    set.add(stringBuffer.toString());
                }
            }
        }
        return set;
    }
}
